package demo1;

public class LeetCode76 {
    public String minWindow(String s, String t) {
        char[] arr1 = s.toCharArray();
        char[] arr2 = t.toCharArray();
        int ns = arr1.length, nt = arr2.length;
        int tmp = ns + 1, begin = -1;
        int[] hash1 = new int[128];  //统计字符串t中字符的频次
        int[] hash2 = new int[128];  //统计窗口中的字符频数
        int kinds = 0;  //统计t中，有多少中字符
        for(char ch : arr2)
            if(hash1[ch]++ == 0) kinds++;
        for(int left = 0, right = 0, count = 0; right < ns; right++) {
            char in = arr1[right];
            if(++hash2[in] == hash1[in]) count++;  //进窗口 + 维护count
            while(kinds == count) {  //判断
                //更新结果
                if(right - left + 1 < tmp) {
                    begin = left;
                    tmp = right - left + 1;
                }
                char out = arr1[left++];
                if(hash2[out]-- == hash1[out]) count--;  //出窗口 + 维护count
            }
        }
        if(begin == -1) return new String();
        else return s.substring(begin, begin + tmp);
    }
}
